Median of Two Sorted Arrays
Leetcode #4 | Hard | Бин. поиск | Математика
Идея
Big-O
- Время
O(log(min(n,m))) - Память
O(1)
Код
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int halfLen = (m+n+1) / 2;
int l = -1;
int r = m+1;
while (r-l > 1) {
int i = (l+r)/2;
int j = halfLen - i;
int Aleft = (i==0) ? Integer.MIN_VALUE : nums1[i-1];
int Bright = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (Aleft > Bright) {
r = i;
} else {
l = i;
}
}
int i = l;
int j = halfLen - i;
int Aleft = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int Aright = (i == m) ? Integer.MAX_VALUE : nums1[i];
int Bleft = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int Bright = (j == n) ? Integer.MAX_VALUE : nums2[j];
if ((m + n) % 2 == 1) {
return Math.max(Aleft, Bleft);
} else {
return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2.0;
}
}
}